- Pradinių duomenų failas:
- hanoj.in
- Rezultatų failas:
- hanoj.out
- Laiko apribojimas:
- 1 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
Hanojaus bokštų uždavinį 1883 metais suformulavo prancūzų matematikas Eduardas Lukas (Edouard Lucas). Duoti trys stiebai ir aštuoni skirtingo dydžio diskai. Iš pradžių visi šie diskai sumauti ant pirmojo stiebo: apačioje pats didžiausias diskas, ant jo – mažesnis ir t. t. Viršuje užmautas pats mažiausias iš diskų. Uždavinys prašo perkelti visus diskus nuo pirmojo stiebo ant paskutiniojo laikantis tokių taisyklių:
- Vienu ėjimu galima kelti tik vieną diską.
- Diską galima užmauti tik ant tuščio stiebo, arba uždėti ant didesnio už jį disko.
Mes praplėsime standartinę uždavinio formuluotę: vietoje aštuonių, reikia perkelti N diskų. Mūsų uždavinyje stiebai yra pavadinti raidėmis A, B ir C. Parašykite programą, kuri atspausdintų ėjimus, kuriuos reikia atlikti, kad diskus perkeltume nuo stiebo A ant stiebo C, laikantis minėtųjų taisyklių. Atliekamų ėjimų skaičius turi būti minimalus.
Pradiniai duomenys
Pradinių duomenų faile įrašytas vienintelis sveikas skaičius N (1 <= N <= 15) – diskų skaičius.
Rezultatai
Rezultatų failą turi sudaryti seka ėjimų, kuriuos atlikus, visi diskai būtų perkelti nuo stiebo A ant stiebo C. Ėjimas aprašomas formatu X -> Y (čia X ir Y yra stiebų vardai A, B arba C). Užrašas X -> Y reiškia, kad nuo stiebo X reikia paimti mažiausią (taigi viršuje esantį) diską ir užmauti ant stiebo Y.
Pavyzdžiai
| Pradiniai duomenys | Rezultatai |
|---|---|
3 |
A -> C A -> B C -> B A -> C B -> A B -> C A -> C |